1. Field of Invention
This invention relates to optimizing variable-length codes used in entropy encoding for use in data compression in accordance, and fully compatible, with the Joint Photographic Experts Group (JPEG) international standard for color image compression. Further description of that standard is made in ISO International Standard DIS 10918-1: Digital Compression Encoding of Continuous Tone Still Image Part 1, Requirements and Guidelines (also included in CCITT Recommendation T.81), and the disclosure of which is incorporated by reference. This invention relates to a method to achieve optimization without buffering the uncompressed image data. In a preferred embodiment of the invention the variable-length coding method is the Huffman coding procedure used in the JPEG standard.
2. Description of Related Art
JPEG image compression is a technique for compressing images using a set of image compression functions. JPEG comprises several steps for data compression: discrete cosine transformation (DCT), quantization, differential pulse-code modulation of the DC DCT coefficients (DC DPCM), zig-zag ordering, zero-run-length counting and entropy encoding. The images compressed with the JPEG compression are digital images.
Prior to compressing an original image, the original image must be sampled along a set of scan lines located at regular distances from each other. The sampled information scanned along each scan line is then converted into binary numbers which may be stored in a memory. The binary numbers, which represent a digital image, and which in turn represent the original image, are the data on which JPEG compression is performed.
The amount of data in a digital image can be extremely large--even millions of bytes. Assuming one byte per pixel, a very-low-resolution 320.times.240 pixel image occupies 76,800 bytes of memory. A document of 81/2.times.11 inches, optically scanned at a resolution of 600 pixels per inch (ppi), generates images of 5100.times.6600 pixels, i.e. more than 30 million pixels. At one byte per pixel, more than 30 megabytes are required to store a single color plane. Color images for display or printing can require more than three times more memory to store the different color planes. Image compression is used to reduce the cost associated with storing of this digital image data and the cost and time associated with transmitting the data. That is, image compression is used to represent original images with less data to reduce storage and transmission costs and the transmission time.
FIG. 1 illustrates a JPEG compression system. As illustrated in FIG. 1, an original image is scanned, using a scanner, digital camera or the like, and sampled to produce a digital image. The binary data symbolizing the image is then processed using DCT to, ideally, produce uncorrelated coefficients. Each DCT coefficient is the amplitude of a specific cosine basis function. The principle of decorrelation of DCT coefficients is used during compression since each resulting coefficient can be further processed independently from other resulting coefficients without significant impact in compression efficiency. The DCT coefficients can also be further quantized using visually-weighted quantization values. Quantization is essentially a process of scaling the DCT coefficients and truncating them to integer values. Zig-zag ordering is a specific sequential ordering of the DCT coefficients from approximately the lowest spatial frequency to the highest spatial frequency.
As illustrated in FIG. 1, entropy encoding is the last step in JPEG compression. Run-length counting is the process of counting the number of zero DCT coefficients preceding a non-zero DCT coefficient within a zig-zag ordered DCT coefficients path to produce symbols representing the information of the DCT coefficients themselves and the number of preceding zeros. Entropy encoding employs a variable length code which actually generates the compressed data. Variable-length encoding requires that the code tables used during encoding be known at the start of encoding. In one type of entropy coding, Huffman encoding assigns a specific length code to each input symbol in the data depending on the assumed frequency of incidence of that symbol, aiming to minimize the average codeword length. The Huffman table contains these variable length codes. The Huffman table must be known in the Huffman encoder and in a Huffman decoder at a transmission destination or process termination point, for example, when displaying or printing the image.
The compression provided by Huffman encoding is a function of the frequency of the input symbols and a function of the length of the Huffman codes assigned to each symbol. JPEG often employs default Huffman tables, which are derived for standard continuous tone (contone) images, such as photographs. The default Huffman tables used in the JPEG standard have characteristics derived from distinctive image statistics that often differ from the characteristics of a Huffman table derived for use with specific images and applications. Examples of those applications include color facsimile transmission and in other applications using mixed raster content (MRC) segmented technology. In MRC, the contents of the images to be compressed under JPEG are parsed apart beforehand in such a way that planes may contain large amounts of background information, i.e., areas of constant color. Because the default Huffman tables are formulated for images that are not often encountered in color facsimile or other MRC based applications, the default Huffman tables do not efficiently or optimally encode the images usually encountered in these applications.
Conventionally, Huffman codes optimized for particular applications can improve the image quality and the compression ratio. The Huffman codes can be optimized by computing the actual frequency of the input symbols for the particular image to be compressed rather than relying on the default JPEG Huffman tables. FIG. 2 illustrates a conventional JPEG compression system that develops optimized Huffman codes and tables. As illustrated in FIG. 2, conventionally optimizing a Huffman table requires two passes over the whole DCT image data. The first pass determines the frequency of the input symbols and produces the optimized Huffman codes for the Huffman tables. The second pass actually encodes the image using the optimized Huffman table.